package oj;

public class Num897 {
    public TreeNode increasingBST(TreeNode root) {
        if(root==null ){
            return null;
        }
        TreeNode newRoot=increasingBST(root.left);//先转换左子树
        TreeNode leftTail=newRoot;
        while (leftTail!=null && leftTail.right!=null){
            leftTail=leftTail.right;//此时leftTail指向转换后左子树的最后一个节点
        }
        if(leftTail!=null){
            leftTail.left=null;
            leftTail.right=root;  //将转换后的左子树与根节点连接
        }
        //将根节点的左节点置空
        root.left=null;
        TreeNode rightHead=increasingBST(root.right);
        if(rightHead!=null){
            root.right=rightHead;
        }
        return newRoot==null?root:newRoot;
    }
}
